package 蓝桥杯算法;

import 二叉树.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class day13 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(
                        new TreeNode(4),
                        2,
                        new TreeNode(6)
                ),
                1,
                new TreeNode(
                        new TreeNode(6),
                        2,
                        new TreeNode(4)
                )
        );
        day13 a=new day13();
        List<String> sb=a.BinaryTreeePaths(root);
        System.out.println(sb.toString());
        System.out.println(a.getLeftLeaf2(root));
        System.out.println(a.findBottomlet(root));
        System.out.println( a.findpath(root,9).toString());

    }
    public boolean isBalanced(TreeNode root){//判断平衡
        return getHight(root)!=-1;
    }
    public int getHight (TreeNode root){//不去记录，找到唯一一个就不符
        if(root==null){
            return 0;
        }
        int leftHeight=getHight(root.left);
        if(leftHeight==-1){
            return -1;
        }
        int rightHeight=getHight(root.right);
        if(rightHeight==-1){
            return -1;
        }
        if(Math.abs(leftHeight-rightHeight)>1){
            return -1;
        }
        return Math.max(leftHeight,rightHeight)+1;
    }
    public List<String> BinaryTreeePaths(TreeNode root){//求路径
        List<String> res=new ArrayList<>();
        if(root==null){
            return res;
        }
        List<Integer> path=new ArrayList<>();
        traversal(root,path,res);
        return res;
    }
    public void traversal(TreeNode root,List<Integer> path,List<String> res){
        path.add(root.val);//每次递归的首要任务
        if(root.left==null&&root.right==null){
            StringBuilder sb=new StringBuilder();
            for(int i=0;i<path.size()-1;i++){
                sb.append(path.get(i)).append("->");
            }
            sb.append(path.get(path.size()-1));
            res.add(sb.toString());
            return;
        }
        if(root.left!=null){
            traversal(root.left,path,res);
            path.remove(path.size()-1);//除去最后一个，方便回溯
        }
        if(root.right!=null){
            traversal(root.right,path,res);
            path.remove(path.size()-1);
        }
    }
    public int getLeftLeaf(TreeNode root){//求左叶子结点的和
        if(root==null){
            return 0;
        }
        int leftValue=getLeftLeaf(root.left);
        int rightValue=getLeftLeaf(root.right);
        int midValue=0;
        if(root.left!=null&&root.left.left==null&&root.left.right==null){
            midValue=root.left.val;
        }
        int sum=midValue+leftValue+rightValue;
        return sum;
    }
    public int getLeftLeaf2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int sum = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.add(node.left);//
                    if (node.left.left == null && node.left.right == null) {
                        sum = sum + node.left.val;
                    }
                }
                if (node.right != null) {//加入节点的主要方法
                    queue.add(node.right);
                }

            }
        }
        return sum;
    }
    int value=0;
    int depth=-1;
    public int findBottomlet(TreeNode root){//求最低端左侧的值
        value=root.val;
        findLeatValue(root,0);
        return value;
    }
    public void findLeatValue(TreeNode node,int deep){
        if(node==null){
            return;
        }
        if(node.left==null&&node.right==null){
            if(deep>depth){
                value=node.val;
                depth=deep;
            }
        }
        if(node.left!=null){//先遍历左侧，说明现在左侧找
            findLeatValue(node.left,deep+1);
        }
        if(node.right!=null){
            findLeatValue(node.right,deep+1);
        }
    }
    public int findBottomlet1(TreeNode root){
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        int res=0;
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode poll=queue.poll();
                if(i==0){//保证是最左侧的值
                    res=poll.val;
                }
                if(poll.left!=null){
                    queue.add(poll.left);
                }
                if(poll.right!=null){
                    queue.add(poll.right);
                }
            }
        }
        return res;
    }
    public List<String> findpath(TreeNode node,int key){
        if(node==null){
            return null;
        }
        List<String> res=new ArrayList<>();
        List<Integer> path=new ArrayList<>();

        traversal3(node,res,path,key);
        return res;
    }


    public void traversal3(TreeNode node,List<String> res,List<Integer> path,int key){
        path.add(node.val);
        if(node==null){
            return;
        }
        int sum=0;
        if(node.left==null&&node.right==null){
            for(int i=0;i<path.size();i++){
                sum+=path.get(i);
            }
            if(sum==key){
                StringBuilder sb=new StringBuilder();
                for(int i=0;i<path.size()-1;i++){
                    sb.append(path.get(i)).append("->");
                }
                sb.append(path.get(path.size()-1));
                res.add(sb.toString());
            }
        }
        if(node.left!=null){
            traversal3(node.left,res,path,key);
            path.remove(path.size()-1);
        }
        if(node.right!=null){
            traversal3(node.right,res,path,key);
            path.remove(path.size()-1);
        }
    }

}
